package leetcode;

import java.util.HashMap;
import java.util.Map;

public class Leetcode146 {
    class LRUCache {
        class DListNode{
            private int key;
            private int value;
            DListNode pre;
            DListNode next;
            public DListNode(){

            }
            public DListNode(int key,int value){
                this.key = key;
                this.value = value;
            }
        }
        private int size;
        private Map<Integer,DListNode> m = new HashMap<>();
        private int capacity;
        private DListNode head;
        private DListNode tail;

        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            head = new DListNode();
            tail = new DListNode();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            DListNode dListNode = m.get(key);
            if(dListNode==null){
                return -1;
            }

            moveToHead(dListNode);
            return dListNode.value;


        }

        public void put(int key, int value) {
            DListNode dListNode = m.get(key);
            if(dListNode == null){
                dListNode = new DListNode(key,value);
                moveToHead(dListNode);
                m.put(key,dListNode);
                size++;
                if(size>capacity){
                    DListNode tmp = removeTail();
                    m.remove(tmp.key);
                }
            }else{
                dListNode.value = value;
                moveToHead(dListNode);
            }
        }

        public void removeNode(DListNode cur){
            DListNode pre = cur.pre;
            DListNode next = cur.next;
            pre.next = next;
            next.pre = pre;

        }

        public void addToHead(DListNode cur){
            cur.next = head.next.next;
            head.next = cur;
            cur.next.pre = cur;
            cur.pre = head;
        }
        public DListNode removeTail(){
            DListNode res = tail.pre;
            DListNode tmp = tail.pre.pre;
            tmp.next = tail;
            tail.pre = tmp;
            return res;
        }
        public void moveToHead(DListNode cur){
            removeNode(cur);
            addToHead(cur);
        }

    }

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

}
